Some New Results in the Alcuin Number of Graphs

摘要

We prove some results concerning Alcuin number of graphs. First, we classifygraphs which have unique minimum vertex cover. Then we present two necessaryconditions for a graph to be of class two and show why one of them (conditionon common neighbors) is sufficient as well. By using this classificationtheorem, we prove some results about class one and class two graphs such ascartesian product of graphs and classification of regular graphs.